public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] testArr = new int[]{1,2,3};
        System.out.println(test.combinationSum4(testArr, 4));
    }


    public int combinationSum4(int[] nums, int target) {
        /**
         * 组合总数Ⅳ
         * 不知道是不是自己没有休息够，就感觉自己脑子不够用了，很无奈（今天休息，不想整了）
         * 状态表示：
         *  本题本质上是在求排列数，那么按照排列数而言，假设其又三个元素组成，那么显而易见的，每个位置都有n中选法（元素个数）
         *  于是我们固定值，遍历数组，求排列数组成的个数
         *  dp[i]表示 数组中的所有元素挑出一些元素来，元素和为i的排列数的总和
         * 状态转移方程：
         *  dp[i] += i - nums[j]; (此处就是在模拟固定最后一个元素，找到所有排列数)
         * 初始化：
         *  由于是线性dp，因此需要给定初始化 dp[0] = 1; 具体原因是：在dp[1] 时，当1==nums[j]即恰好一个元素就是一个排列方式时，
         *  需要算作一种，因此dp[0] = 1
         * 填表顺序：
         *  从左到右
         * 返回值：
         *  return dp[target];
         * */
        // 1 预处理
        int n = nums.length;
        // 2 创建dp表
        int[] dp = new int[target + 1];
        // 3 初始化
        dp[0] = 1;
        // 4 填表
        for(int i = 1; i <= target; i++) {
            for(int j = 0; j < n; j ++) {
                // 当前元素值小于等于目标值，固定并找前者的排列数
                if(nums[j] <= i) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        // 5 返回值
        return dp[target];
    }
}
